package cn.datastruct.NineGrahp;

import java.util.*;

/**
 * 思路：
 * 1.用二维矩阵Edges来表示图之间的连接关系，weight=1,表示相通，weight=0表示没有连接
 * 2.用ArrayList Vertexs列表来存储节点
 * 3.edgeNums表示节点数目
 * 4.成员方法
 * 4.1.getVertex()获取节点
 * 4.2.getEdges()获取边之间的关系
 * 4.3.addSide(int v1, int v2, int weight)添加边
 * 4.3.Graph(int n) 构造方法
 * 4.4.添加节点addVertex(String s)
 */
public class Graph implements DFS, BFS {
    private int[][] Edges;//用二维矩阵Edges来表示图之间的连接关系，weight=1,表示相通，weight=0表示没有连接
    private ArrayList<String> Vertexs;//用来存储节点
    private int edgeNums;//表示边的数目
    boolean[] isVisited;//默认为false

    public static void main(String[] args) {
        int n = 5;
        String[] Vertex = {"A", "B", "C", "D", "E", "F"};
        Graph graph = new Graph(6);
        for (String vertex : Vertex) {
            graph.addVertex(vertex);
        }
        graph.addSide(0, 1, 1);
        graph.addSide(0, 2, 1);
        graph.addSide(1, 2, 1);
        graph.addSide(1, 3, 1);
        graph.addSide(1, 4, 1);
        graph.addSide(2, 4, 1);
        graph.addSide(3, 5, 1);
        graph.showEdges();
        graph.dfs();

    }

    //构造方法
    public Graph(int n) {
        Edges = new int[n][n];
        edgeNums = 0;
        Vertexs = new ArrayList<>();
        isVisited = new boolean[n];
    }

    //获取节点通过index
    public String valueByIndex(int index) {
        return Vertexs.get(index);
    }

    //添加节点
    public void addVertex(String s) {
        this.Vertexs.add(s);
    }

    //得到节点数
    public int getVertex() {
        return this.Vertexs.size();
    }

    //得到边与边之间的关系
    public void showEdges() {
        for (int[] edge : Edges) {
            System.out.println(Arrays.toString(edge));
        }
    }

    public int getEdge(int v1, int v2) {
        return Edges[v1][v2];
    }
    //添加边

    /**
     * @param v1     第一个节点
     * @param v2     第二个节点
     * @param weight 节点之间的权重
     */
    public void addSide(int v1, int v2, int weight) {
        this.Edges[v1][v2] = weight;
        this.Edges[v2][v1] = weight;
        this.edgeNums++;
    }

    //得到第一个邻接节点的下标w
    @Override
    public int getNeighbor(int index) {
        int length = Vertexs.size();
        for (int i = 0; i < length; i++) {
            if (Edges[index][i] > 0) {//存在节点
                return i;
            }
        }
        return -1;
    }

    //根据前一个邻接节点的下标来获取下一个下标
    @Override
    public int getNextNeighbor(int v1, int v2) {
        int length = Vertexs.size();
        for (int i = v2 + 1; i < length; i++) {
            if (Edges[v1][i] > 0) {
                return i;
            }
        }
        return -1;
    }

    @Override
    public void dfs(boolean[] isVisited, int index) {
        System.out.printf("%s\t", valueByIndex(index));
        //开始遍历
        isVisited[index] = true;
        //得到邻接下标
        int w = getNeighbor(index);
        while (w != -1) {
            if (!isVisited[w]) {
                dfs(isVisited, w);
            }
            w = getNextNeighbor(index, w);
        }
    }

    @Override
    public void dfs() {
        int length = Vertexs.size();
        for (int i = 0; i < length; i++) {
            if (!isVisited[i]) {
                dfs(isVisited, i);
            }
            ;
        }
    }

    @Override
    public void bfs() {
        int length = Vertexs.size();
        for (int i = 0; i < length; i++) {
            if (!isVisited[i])
                bfs(isVisited, i);
        }
    }

    @Override
    public void bfs(boolean[] isVisited, int index) {
        int u;//表示队列头节点对应的下标
        int w;//邻接节点w

        //队列记录节点访问顺序
        LinkedList queue = new LinkedList();
        System.out.println(valueByIndex(index) + "->");
        //标记为已访问
        queue.addLast(index);
        while (!queue.isEmpty()) {
            u = (Integer) queue.removeFirst();
            w = getNeighbor(index);
            //得到邻接节点
            while (w != -1) {
                if (!isVisited[w]) {
                    isVisited[w] = true;
                    System.out.println(valueByIndex(w));
                    queue.addLast(w);
                }
                w = getNextNeighbor(u, w);//体现出广度遍历
            }
        }
    }
}
